class Solution {
public:
    int find(vector<int>& nums,int l,int r){
        int m = l + (r - l) / 2;
        if(l > r){
            return -1;
        }
        
        int left = find(nums,l,m-1);
        if(left != -1){
            return left;
        }else if(nums[m] == m){
            return m;
        }
        
        return find(nums,m+1,r);
    }
    
    int findMagicIndex(vector<int>& nums) {
        int n = nums.size();
        return find(nums,0,n-1);
    }
};
